home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-13 / tde3.zip / SORT.C < prev    next >
C/C++ Source or Header  |  1993-06-05  |  24KB  |  725 lines
  1. /*
  2.  * These functions sort lines according to keys in a marked BOX block.
  3.  *
  4.  * Being that the data structure was changed from a big text buffer to a
  5.  * linked list, we can replace the simple insertion sort algorithm with a
  6.  * much faster sort algorithm.  The classic search and sort reference is by
  7.  * Donald E. Knuth, _The Art of Computer Programming; Volume 3:  Sorting and
  8.  * Searching_.  One of the fastest and most widely used general purpose
  9.  * sorting algorithms is the "Quicksort" algorithm.
  10.  *
  11.  * For implementation hints and guidelines on the Quicksort algorithm, one
  12.  * might read the original Quicksort paper by C. A. R. Hoare or anything
  13.  * by Robert Sedgewick.  Although Dr. Sedgewick includes a chapter on
  14.  * Quicksort in his intro computer science textbooks, _Algorithms in X_,
  15.  * I prefer the detailed hints and guidelines in his 1978 CACM paper.
  16.  * Incidentally, Dr. Sedgewick's Ph.D. dissertation was on the modification
  17.  * and mathematical analysis of the Quicksort algorithm.
  18.  *
  19.  *
  20.  * See:
  21.  *
  22.  *   Charles Antony Richard Hoare, "Algorithm 63: Partition."  _Communications
  23.  *      of the ACM_, 4 (No. 7): 321, 1961.
  24.  *
  25.  *   Charles Antony Richard Hoare, "Algorithm 64: Quicksort."  _Communications
  26.  *      of the ACM_, 4 (No. 7): 321, 1961.
  27.  *
  28.  *   Charles Antony Richard Hoare, "Quicksort."  _The Computer Journal_,
  29.  *      5 (April 1962 - January 1963): 10-15, 1962.
  30.  *
  31.  * See also:
  32.  *
  33.  *   Donald Ervin Knuth, _The Art of Computer Programming; Volume 3:  Sorting
  34.  *     and Searching_, Addison-Wesley, Reading, Mass., 1973, Chapter 5,
  35.  *     Sorting, pp 114-123.  ISBN 0-201-03803-X.
  36.  *
  37.  *   Robert Sedgewick, "Implementing Quicksort Programs."  _Communications
  38.  *      of the ACM_, 21 (No. 10): 847-857, 1978.
  39.  *
  40.  *
  41.  *                           Quicksort in TDE
  42.  *
  43.  * Quicksort in TDE is a stable, non-recursive implementation based on
  44.  * Program 2, page 851, CACM, 21 (No. 10), 1978, by Robert Sedgewick.  My
  45.  * partition algorithm finds the median-of-three.  Then, it walks from the
  46.  * head of the list, comparing nodes, and uses the first occurrence of the
  47.  * key of the median-of-three as the partition node.  Mostly by accident
  48.  * and partly by design, my partition routine uses a "fat pivot" to keep
  49.  * equal nodes in the same relative order as they appear in the file (the
  50.  * definition of a stable sort).  By using the first median-of-three node
  51.  * as the partitioning node, 1) sorting a sorted list is fairly fast and
  52.  * 2) encountering a worst case is very unlikely.  TDE will sort, fairly
  53.  * fast, multiple keys ascending or descending, ignore or match case, and
  54.  * preserve order in the file, while using a custom sort sequence for your
  55.  * favorite domestic or foreign language.
  56.  *
  57.  *
  58.  * New editor name:  TDE, the Thomson-Davis Editor.
  59.  * Author:           Frank Davis
  60.  * Date:             June 5, 1991, version 1.0
  61.  * Date:             July 29, 1991, version 1.1
  62.  * Date:             October 5, 1991, version 1.2
  63.  * Date:             January 20, 1992, version 1.3
  64.  * Date:             February 17, 1992, version 1.4
  65.  * Date:             April 1, 1992, version 1.5
  66.  * Date:             June 5, 1992, version 2.0
  67.  * Date:             October 31, 1992, version 2.1
  68.  * Date:             April 1, 1993, version 2.2
  69.  * Date:             June 5, 1993, version 3.0
  70.  *
  71.  * This code is released into the public domain, Frank Davis.
  72.  * You may use and distribute it freely.
  73.  */
  74.  
  75. #include "tdestr.h"
  76. #include "common.h"
  77. #include "tdefunc.h"
  78. #include "define.h"
  79.  
  80.  
  81. /*
  82.  * Name:    sort_box_block
  83.  * Purpose: sort lines according to text in marked BOX block
  84.  * Date:    June 5, 1992
  85.  * Passed:  window:  pointer to current window
  86.  * Notes:   quick sort and insertion sort the lines in the BOX buff according
  87.  *           to stuff in a box block.
  88.  */
  89. int  sort_box_block( WINDOW *window )
  90. {
  91. int  prompt_line;
  92. int  block_type;
  93. line_list_ptr ll;
  94. register file_infos *file;
  95. WINDOW *sw;
  96. int  rc;
  97. char line_buff[(MAX_COLS+1)*2]; /* buffer for char and attribute  */
  98.  
  99.    /*
  100.     * make sure block is marked OK
  101.     */
  102.    rc = OK;
  103.    prompt_line = window->bottom_line;
  104.    entab_linebuff( );
  105.    if (un_copy_line( window->ll, window, TRUE ) == ERROR)
  106.       return( ERROR );
  107.    check_block( );
  108.    if (g_status.marked == TRUE) {
  109.       file  = g_status.marked_file;
  110.       block_type = file->block_type;
  111.       if (block_type == BOX) {
  112.          /*
  113.           * sort ascending or descending?
  114.           */
  115.          rc = get_sort_order( window );
  116.          if (rc != ERROR) {
  117.             file->modified = TRUE;
  118.             if (mode.do_backups == TRUE) {
  119.                sw = g_status.window_list;
  120.                for (; ptoul( sw->file_info ) != ptoul( file );)
  121.                   sw = sw->next;
  122.                backup_file( sw );
  123.             }
  124.  
  125.             /*
  126.              * figure the width of the block.
  127.              */
  128.             sort.block_len = file->block_ec + 1 - file->block_bc;
  129.  
  130.             /*
  131.              * save the prompt line and print the quicksort message.
  132.              */
  133.             save_screen_line( 0, prompt_line, line_buff );
  134.             eol_clear( 0, prompt_line, g_display.text_color );
  135.             set_prompt( block22a, prompt_line );
  136.  
  137.             /*
  138.              * set up the sort structure.
  139.              */
  140.             sort.bc  = g_status.marked_file->block_bc;
  141.             sort.ec  = g_status.marked_file->block_ec;
  142.             sort.order_array = (mode.search_case == IGNORE) ?
  143.                                     sort_order.ignore : sort_order.match;
  144.  
  145.             /*
  146.              * save the previous node for use with insertion sort.
  147.              */
  148.             ll = file->block_start->prev;
  149.             quick_sort_block( file->block_br, file->block_er,
  150.                               file->block_start, file->block_end );
  151.  
  152.             /*
  153.              * get back previous node and clean up list with insertion
  154.              *   sort.
  155.              */
  156.             if (ll == NULL)
  157.                ll = file->line_list;
  158.             else
  159.                ll = ll->next;
  160.             set_prompt( block22b, prompt_line );
  161.             insertion_sort_block( file->block_br, file->block_er, ll );
  162.  
  163.             /*
  164.              * housekeeping.  mark the file as dirty and restore the
  165.              *   cursors, which are scrambled during the sort.
  166.              */
  167.             file->dirty = GLOBAL;
  168.             restore_cursors( file );
  169.             restore_screen_line( 0, prompt_line, line_buff );
  170.          }
  171.       } else {
  172.          /*
  173.           * can only sort box blocks
  174.           */
  175.          error( WARNING, prompt_line, block23 );
  176.          rc = ERROR;
  177.       }
  178.    } else {
  179.       /*
  180.        * box not marked
  181.        */
  182.       error( WARNING, prompt_line, block24 );
  183.       rc = ERROR;
  184.    }
  185.    return( rc );
  186. }
  187.  
  188.  
  189. /*
  190.  * Name:    quick_sort_block
  191.  * Purpose: sort lines according to text in marked BOX block
  192.  * Date:    Jaunary 10, 1993
  193.  * Passed:  low:        starting line in box block
  194.  *          high:       ending line in a box block
  195.  *          low_node:   starting node in box block
  196.  *          high_node:  ending node in box block
  197.  * Notes:   Quicksort lines in the BOX block according to keys in
  198.  *           a box block.
  199.  *          because the median of three method is used to find the partion
  200.  *           node,  high - low  should be greater than or equal to 2.
  201.  *          with end recursion removal and sorting the smallest sublist
  202.  *           first, our stack only needs room for log2 (N+1)/(M+2) nodes.
  203.  *           a stack size of 24 can reliably handle almost 500 million lines.
  204.  */
  205. void quick_sort_block( long low, long high, line_list_ptr low_node,
  206.                        line_list_ptr high_node )
  207. {
  208. long low_rline_stack[24];
  209. long high_rline_stack[24];
  210. line_list_ptr low_node_stack[24];
  211. line_list_ptr high_node_stack[24];
  212. long low_count;
  213. long high_count;
  214. long count;
  215. line_list_ptr low_start;
  216. line_list_ptr low_head;
  217. line_list_ptr low_tail;
  218. line_list_ptr high_end;
  219. line_list_ptr high_head;
  220. line_list_ptr high_tail;
  221. line_list_ptr equal_head;
  222. line_list_ptr equal_tail;
  223. line_list_ptr walk_node;
  224. line_list_ptr median_node;
  225. int  i;
  226. int  stack_pointer;
  227.  
  228.    assert( low_node->len != EOF);
  229.    assert( high_node->len != EOF);
  230.  
  231.    stack_pointer = 0;
  232.    while (TRUE) {
  233.  
  234.       /*
  235.        * being that a median-of-three is used as the partition algorithm,
  236.        *  we probably need to have at least 2 nodes in each sublist.  I
  237.        *  chose a minimum of 25 nodes as a SWAG (scientific wild ass guess).
  238.        *  a simple insertion sort mops the list after quicksort finishes.
  239.        */
  240.       while (high - low > 25) {
  241.  
  242.          assert( high >= 1 );
  243.          assert( low  >= 1 );
  244.          assert( low  <= high );
  245.  
  246.          /*
  247.           * start the walk node at the head of the list and walk to the
  248.           *  middle of the sublist.
  249.           */
  250.          walk_node  = low_node;
  251.          count = (high - low) / 2;
  252.          for (; count > 0; count--)
  253.             walk_node = walk_node->next;
  254.  
  255.          /*
  256.           * now, find the median of the low, middle, and high node.
  257.           *
  258.           * being that I am subject to error, let's assert that we really
  259.           *  did find the median-of-three.
  260.           */
  261.          load_pivot( low_node );
  262.          if (compare_pivot( walk_node ) < 0) {
  263.             low_head   = walk_node;
  264.             median_node = low_node;
  265.          } else {
  266.             low_head   = low_node;
  267.             median_node = walk_node;
  268.          }
  269.          high_head = high_node;
  270.          load_pivot( median_node );
  271.          if (compare_pivot( high_node ) < 0) {
  272.             high_head   = median_node;
  273.             median_node = high_node;
  274.          }
  275.          load_pivot( median_node );
  276.          if (compare_pivot( low_head ) > 0) {
  277.             low_tail    = median_node;
  278.             median_node = low_head;
  279.             low_head    = low_tail;
  280.          }
  281.  
  282.          load_pivot( median_node );
  283.  
  284.          assert( compare_pivot( low_head ) <= 0 );
  285.          assert( compare_pivot( high_head ) >= 0 );
  286.  
  287.          /*
  288.           * now, walk again from the head of the list comparing nodes and
  289.           *  use the first occurrence of the median node as the partition.
  290.           */
  291.          walk_node = low_node;
  292.          for (i = 0; ; walk_node = walk_node->next) {
  293.             if (compare_pivot( walk_node ) == 0)
  294.                break;
  295.             i = 1;
  296.          }
  297.  
  298.          /*
  299.           * initialize pointers and counters for this partition.
  300.           */
  301.          low_start  = low_node->prev;
  302.          high_end   = high_node->next;
  303.          low_head   = low_tail  = NULL;
  304.          high_head  = high_tail = NULL;
  305.          low_count  = high_count = 0;
  306.  
  307.          /*
  308.           * setup the first occurrence of the median node as a "fat pivot"
  309.           *  sublist.  there are two cases to consider 1) the first
  310.           *  occurrence of the median node is the first element in the
  311.           *  sublist, i == 0, or 2) the first occurrence of the median node
  312.           *  is somewhere in the sublist.
  313.           */
  314.          if (i == 0)
  315.             walk_node = equal_head = equal_tail = low_node;
  316.          else {
  317.             equal_head = equal_tail = walk_node;
  318.             equal_head->next->prev = equal_head->prev;
  319.             equal_head->prev->next = equal_head->next;
  320.             equal_head->next = low_node;
  321.             walk_node = equal_head;
  322.          }
  323.          load_pivot( equal_head );
  324.  
  325.          /*
  326.           * PARTITION:
  327.           *  put all nodes less than the pivot on the end of the low list.
  328.           *  put all nodes equal to the pivot on the end of the equal list.
  329.           *  put all nodes greater than the pivot on the end of the high list.
  330.           */
  331.          for (count=low+1; count <= high; count++) {
  332.             walk_node = walk_node->next;
  333.             i = compare_pivot( walk_node );
  334.             if (i > 0) {
  335.                if (high_head == NULL)
  336.                   high_head = high_tail = walk_node;
  337.                else {
  338.                   high_tail->next = walk_node;
  339.                   walk_node->prev = high_tail;
  340.                   high_tail = walk_node;
  341.                }
  342.  
  343.                /*
  344.                 * keep a count of the number of nodes in the high list.
  345.                 */
  346.                ++high_count;
  347.             } else if (i < 0) {
  348.                if (low_head == NULL)
  349.                   low_head = low_tail = walk_node;
  350.                else {
  351.                   low_tail->next = walk_node;
  352.                   walk_node->prev = low_tail;
  353.                   low_tail = walk_node;
  354.                }
  355.  
  356.                /*
  357.                 * keep a count of the number of nodes in the low list
  358.                 */
  359.                ++low_count;
  360.             } else {
  361.                equal_tail->next = walk_node;
  362.                walk_node->prev = equal_tail;
  363.                equal_tail = walk_node;
  364.             }
  365.          }
  366.  
  367.          assert( low_count >= 0 );
  368.          assert( low_count < high - low );
  369.          assert( high_count >= 0 );
  370.          assert( high_count < high - low );
  371.  
  372.          /*
  373.           * we just partitioned the sublist into low, equal, and high
  374.           *  sublists.  now, let's put the lists back together.
  375.           */
  376.          if (low_count > 0) {
  377.             low_head->prev = low_start;
  378.             if (low_start != NULL)
  379.                low_start->next = low_head;
  380.             else
  381.                g_status.marked_file->line_list = low_head;
  382.             low_tail->next = equal_head;
  383.             equal_head->prev = low_tail;
  384.          } else {
  385.             equal_head->prev = low_start;
  386.             if (low_start != NULL)
  387.                low_start->next = equal_head;
  388.             else
  389.                g_status.marked_file->line_list = equal_head;
  390.          }
  391.          if (high_count > 0) {
  392.             high_head->prev = equal_tail;
  393.             equal_tail->next = high_head;
  394.             high_tail->next = high_end;
  395.             high_end->prev  = high_tail;
  396.          } else {
  397.             equal_tail->next = high_end;
  398.             high_end->prev   = equal_tail;
  399.          }
  400.  
  401.          /*
  402.           * now, lets look at the low list and the high list.  save the node
  403.           *  pointers and counters of the longest sublist on the stack.
  404.           *  then, quicksort the shortest sublist.
  405.           */
  406.          if (low_count > high_count) {
  407.  
  408.             /*
  409.              * if fewer than 25 nodes in the high count, don't bother to
  410.              *  push the stack -- sort the low list.
  411.              */
  412.             if (high_count > 25) {
  413.                low_rline_stack[stack_pointer]  = low;
  414.                high_rline_stack[stack_pointer] = low + low_count - 1;
  415.                low_node_stack[stack_pointer]   = low_head;
  416.                high_node_stack[stack_pointer]  = low_tail;
  417.                ++stack_pointer;
  418.                low       = high - high_count + 1;
  419.                high      = high;
  420.                low_node  = high_head;
  421.                high_node = high_tail;
  422.             } else {
  423.                low       = low;
  424.                high      = low + low_count - 1;
  425.                low_node  = low_head;
  426.                high_node = low_tail;
  427.             }
  428.          } else {
  429.  
  430.             /*
  431.              * if fewer than 25 nodes in the low count, don't bother to
  432.              *  push the stack -- sort the high list.
  433.              */
  434.             if (low_count > 25) {
  435.                low_rline_stack[stack_pointer]  = high - high_count + 1;
  436.                high_rline_stack[stack_pointer] = high;
  437.                low_node_stack[stack_pointer]   = high_head;
  438.                high_node_stack[stack_pointer]  = high_tail;
  439.                ++stack_pointer;
  440.                low       = low;
  441.                high      = low + low_count - 1;
  442.                low_node  = low_head;
  443.                high_node = low_tail;
  444.             } else {
  445.                low       = high - high_count + 1;
  446.                high      = high;
  447.                low_node  = high_head;
  448.                high_node = high_tail;
  449.             }
  450.          }
  451.  
  452.          assert( stack_pointer < 32 );
  453.       }
  454.  
  455.       /*
  456.        * now that we have sorted the smallest sublist, we need to pop
  457.        *  the long sublist(s) that were pushed on the stack.
  458.        */
  459.       --stack_pointer;
  460.       if (stack_pointer < 0)
  461.          break;
  462.       low       = low_rline_stack[stack_pointer];
  463.       high      = high_rline_stack[stack_pointer];
  464.       low_node  = low_node_stack[stack_pointer];
  465.       high_node = high_node_stack[stack_pointer];
  466.    }
  467. }
  468.  
  469.  
  470. /*
  471.  * Name:    insertion_sort_block
  472.  * Purpose: sort small partitions passed in by qsort
  473.  * Date:    January 10, 1993
  474.  * Passed:  low:          starting line in box block
  475.  *          high:         ending line in a box block
  476.  *          first_node:   first linked list node to sort
  477.  * Notes:   Insertion sort the lines in the BOX buff according to stuff in
  478.  *           a box block.
  479.  */
  480. void insertion_sort_block( long low, long high, line_list_ptr first_node )
  481. {
  482. long down;                      /* relative line number for insertion sort */
  483. long pivot;                     /* relative line number of pivot in block */
  484. long count;
  485. line_list_ptr pivot_node;       /* pointer to actual text in block */
  486. line_list_ptr down_node;        /* pointer used to compare text */
  487. text_ptr key;
  488. int  dirty_flag;
  489. int  len;
  490.  
  491.    /*
  492.     * make sure we have more than 1 line to sort.
  493.     */
  494.    if (low < high) {
  495.  
  496.       count = (int)(high - low) + 1;
  497.       pivot_node = first_node->next;
  498.       for (pivot=1; pivot < count; pivot++) {
  499.          load_pivot( pivot_node );
  500.          key = pivot_node->line;
  501.          len = pivot_node->len;
  502.          dirty_flag = pivot_node->dirty;
  503.          down_node = pivot_node;
  504.          for (down=pivot-1; down >= 0; down--) {
  505.             /*
  506.              * lets keep comparing the keys until we find the hole for
  507.              *  pivot.
  508.              */
  509.             if (compare_pivot( down_node->prev ) > 0) {
  510.                down_node->line = down_node->prev->line;
  511.                down_node->len = down_node->prev->len;
  512.                down_node->dirty = down_node->prev->dirty;
  513.             } else
  514.                break;
  515.             down_node = down_node->prev;
  516.          }
  517.          down_node->line = key;
  518.          down_node->len  = len;
  519.          down_node->dirty = (char)dirty_flag;
  520.          pivot_node = pivot_node->next;
  521.       }
  522.    }
  523. }
  524.  
  525.  
  526. /*
  527.  * Name:    load_pivot
  528.  * Purpose: load pivot point for insertion sort
  529.  * Date:    June 5, 1992
  530.  * Passed:  text:  line that contains the pivot
  531.  */
  532. void load_pivot( line_list_ptr node )
  533. {
  534.    sort.pivot_ptr = node->line;
  535.    sort.pivot_len = node->len;
  536. }
  537.  
  538.  
  539. /*
  540.  * Name:    compare_pivot
  541.  * Purpose: compare pivot string with text string
  542.  * Date:    June 5, 1992
  543.  * Passed:  text:  pointer to current line
  544.  * Notes:   the sort structure keeps track of the pointer to the pivot line
  545.  *           and the pivot line length.
  546.  */
  547. int  compare_pivot( line_list_ptr node )
  548. {
  549. register int len;
  550. register int bc;
  551. int  rc;
  552. int  left_over;
  553.  
  554.    len = node->len;
  555.    bc  = sort.bc;
  556.  
  557.    assert( bc >= 0 );
  558.    assert( len >= 0 );
  559.  
  560.    /*
  561.     * is the current line length less than beginning column?  if so, just
  562.     *  look at the length of the pivot line.  no need to compare keys.
  563.     */
  564.    if (len < bc+1) {
  565.       if (sort.pivot_len < bc+1)
  566.          return( 0 );
  567.       else
  568.          return( sort.direction == ASCENDING ?  -1 : 1 );
  569.  
  570.    /*
  571.     * is the pivot line length less than beginning column?  if so, just
  572.     *  look at the length of the current line.  no need to compare keys.
  573.     */
  574.    } else if (sort.pivot_len < bc+1) {
  575.       if (len < bc+1)
  576.          return( 0 );
  577.       else
  578.          return( sort.direction == ASCENDING ?  1 : -1 );
  579.    } else {
  580.  
  581.       /*
  582.        * if lines are of equal length or greater than the ending column,
  583.        *  then lets consider them equal.
  584.        */
  585.       if (len == sort.pivot_len)
  586.          left_over = 0;
  587.       else if (len >= sort.ec  &&  sort.pivot_len >= sort.ec)
  588.          left_over = 0;
  589.       else {
  590.  
  591.          /*
  592.           * if one line does not extend thru the ending column, give
  593.           *  preference to the longest key.
  594.           */
  595.          if (sort.direction == ASCENDING)
  596.             left_over =  len > sort.pivot_len ? 1 : -1;
  597.          else
  598.             left_over =  len > sort.pivot_len ? -1 : 1;
  599.       }
  600.  
  601.       /*
  602.        * only need to compare up to length of the key in the pivot line.
  603.        */
  604.       if (len > sort.pivot_len)
  605.          len = sort.pivot_len;
  606.       len = len - bc;
  607.       if (len > sort.block_len)
  608.          len = sort.block_len;
  609.  
  610.       assert( len > 0 );
  611.  
  612.       if (sort.direction == ASCENDING)
  613.          rc = my_memcmp( node->line + bc, sort.pivot_ptr + bc, len );
  614.       else
  615.          rc = my_memcmp( sort.pivot_ptr + bc, node->line + bc, len );
  616.  
  617.       /*
  618.        * if keys are equal, let's see if one key is longer than the other.
  619.        */
  620.       if (rc == 0)
  621.          rc = left_over;
  622.       return( rc );
  623.    }
  624. }
  625.  
  626.  
  627. /*
  628.  * Name:    my_memcmp
  629.  * Purpose: compare strings using ignore or match case sort order
  630.  * Date:    October 31, 1992
  631.  * Passed:  s1:  pointer to string 1
  632.  *          s2:  pointer to string 2
  633.  *          len: number of characters to compare
  634.  * Notes:   let's do our own memcmp, so we can sort languages that use
  635.  *           extended characters as part of their alphabet.
  636.  */
  637. int  my_memcmp( text_ptr s1, text_ptr s2, int len )
  638. {
  639. unsigned char *p;
  640. register int c;
  641.  
  642.    assert( len >= 0 );
  643.    assert( len < MAX_LINE_LENGTH );
  644.    assert( s1 != NULL );
  645.    assert( s2 != NULL );
  646.  
  647.    if (len == 0)
  648.       return( 0 );
  649.  
  650.    p = sort.order_array;
  651.  
  652.    /*
  653.     * the C comparison function is equivalent to the assembly version;
  654.     *  however, once the assembly routine initializes, it is much faster
  655.     *  than the C version.
  656.     */
  657.    if (len < 10) {
  658.       for (;(c = (int)p[*s1] - (int)p[*s2]) == 0  &&  len > 0;
  659.                                               s1++, s2++, len--);
  660.       return( c );
  661.    } else {
  662.  
  663.       ASSEMBLE {
  664.  
  665.    /*
  666.    ; Register strategy:
  667.    ;   ax  == *s1
  668.    ;   dx  == *s2
  669.    ;   ds:[si]  == s1
  670.    ;   es:[bx]  == s2
  671.    ;   bp       == sort.order_array
  672.    ;   [bp+di]  == p[*s1]  or  p[*s2]
  673.    ;   cx       == len
  674.    ;
  675.    ;  CAVEAT:  sort.order_array is assumed to be located in the stack segment
  676.    */
  677.  
  678.         push    ds                      /* push required registers */
  679.         push    si
  680.         push    di
  681.         push    bp
  682.  
  683.         xor     ax, ax                  /* zero ax */
  684.         mov     cx, WORD PTR len        /* keep len in cx */
  685.         cmp     cx, 0                   /* len <= 0? */
  686.         jle     get_out                 /* yes, get out */
  687.  
  688.         mov     bx, WORD PTR s2         /* load our registers */
  689.         mov     ax, WORD PTR s2+2
  690.         mov     es, ax                  /* es:[bx] = s2 */
  691.         mov     si, WORD PTR s1
  692.         mov     ax, WORD PTR s1+2
  693.         mov     ds, ax                  /* ds:[si] = s1 */
  694.         mov     bp, p                   /* [bp] = p */
  695.         xor     ax, ax                  /* zero out ax */
  696.         xor     dx, dx                  /* zero out dx */
  697.       }
  698. top:
  699.  
  700.    ASSEMBLE {
  701.         mov     al, BYTE PTR ds:[si]    /* al == *s1 */
  702.         mov     di, ax
  703.         mov     al, BYTE PTR [bp+di]    /* al == p[*s1] */
  704.         mov     dl, BYTE PTR es:[bx]    /* dl == *s2 */
  705.         mov     di, dx
  706.         mov     dl, BYTE PTR [bp+di]    /* dl == p[*s2] */
  707.         sub     ax, dx                  /* ax == p[*s1] - p[*s2] */
  708.         jne     get_out
  709.         inc     bx
  710.         inc     si
  711.         dec     cx
  712.         cmp     cx, 0
  713.         jg      top                     /* ax keeps the return value */
  714.       }
  715. get_out:
  716.  
  717.    ASSEMBLE {
  718.         pop     bp                      /* pop the registers we pushed */
  719.         pop     di
  720.         pop     si
  721.         pop     ds                      /* ax keeps the return value */
  722.       }
  723.    }
  724. }
  725.